#!/usr/bin/env python
#encoding: latin1

def expresar_como_perfilciudad(listaedificios):
	resultado = ""
	if (len(listaedificios) > 0):
		resultado += str(listaedificios[0][0])
		contador = 1
		for edificio in listaedificios:
			resultado+=","
			if (int(resultado[len(resultado)-2]) < edificio[0]):
				resultado+= "0,"+ str(edificio[0])+","
			resultado += str(edificio[1])+","+str(edificio[2])
			contador+=1
	return resultado

def leer(archivo):
	"""Pre: el archivo es .txt y su contenido es de (x,y,z) con renglón, siendo x,y,z números enteros. X: representa el punto donde comienza el edificio, Y: representa la altura, Z: representa el punto donde termina del edificio. X siempre es menor estricto que Z. Post: devuelve una lista de listas, donde cada lista dentro de la lista, representa a cada edificio."""
	lista = []
	try:
		edificios = open(archivo)
	except IOError:
		print "El archivo es inválido"
		return None
	for linea in edificios:		
		linea = linea.rstrip('\n')
		datos = linea.strip("(").strip(")")
		datos = datos.split(",")
		try:		
			assert len(datos) == 3
			assert datos[0] < datos[2]
		except AssertionError:
			print "Formato del archivo incorrecto"
			return None

		lista.append(map(int,datos))		
	edificios.close()
	return lista			

def iniciar_programa():
	print "TP2 de Teoría de Algoritmos. Punto 1: Perfil de la ciudad"
	archivo=raw_input("Nombre del archivo a procesar: ")	
	return archivo;

def mergesort_edificios(datos):
	"""Calcula el ejercicio n°1 del TP2"""
	#Caso base 
	if len(datos) < 2:
		return datos

	medio = len(datos) / 2
	izquierda = mergesort_edificios(datos[:medio])
	derecha = mergesort_edificios(datos[medio:])
	return merge(izquierda, derecha)

def merge(lista1, lista2):
	i, j = 0, 0
	resultado = []
	
	while (i < len(lista1) and j < len(lista2)):
		dato_resultado = []
		segundo_dato_resultado = [] 
		dato1 = lista1[i]
		dato2 = lista2[j]		

		if (dato1[0] > dato2[0]) or ((dato1[0] == dato2[0]) and (dato1[1] < dato2[1])):			
			dato_resultado.insert(0,dato2[0])
			dato_resultado.insert(1,dato2[1])		
			dato1 = dato2
			dato2 = lista1[i]
			j += 1
			dato1_esta_en_lista1 = False
		else: 
			dato_resultado.insert(0,dato1[0])
			dato_resultado.insert(1,dato1[1])
			i += 1
			dato1_esta_en_lista1 = True
	
		if (dato1[2] < dato2[0]):
			dato_resultado.insert(2,dato1[2])
		else: #Intersecan
			if (dato2[1] > dato1[1]): #el otro edif esta dentro y es mas alto
				dato_resultado.insert(2,dato2[0])
				if (dato1[2] > dato2[2]): 
					segundo_dato_resultado = [dato2[2], dato1[1], dato1[2]] #divido el edificio en dos segmentos
					if (dato1_esta_en_lista1): lista2.insert(j+1,segundo_dato_resultado)
					else: lista1.insert(i+1,segundo_dato_resultado)
			else:
				dato_resultado.insert(2,dato1[2])
				if (dato2[2] <= dato1[2]): #Si un edificio esta "dentro" de otro y es mas bajito,lo descarta
					if (dato1_esta_en_lista1): j+= 1
					else: i+= 1
				else: #caso q es mas bajito pero tiene un z mayor
					if (dato1_esta_en_lista1): lista2[j][0] = dato1[2]
					else: lista1[i][0] = dato1[2]				

		resultado.append(dato_resultado)

	resultado += lista1[i:]
	resultado += lista2[j:]
	return resultado

def calcular_punto_1(datos):
	resultado = mergesort_edificios(datos)
	return expresar_como_perfilciudad(resultado)
			
def main():
	archivotxt = iniciar_programa()
	datos = leer(archivotxt)
	if (datos == None): return
	resultado = calcular_punto_1(datos)
	print resultado

main()

